﻿#include <iostream>
#include <assert.h>

static int heapSize;

static void swap(int* arr, int index1, int index2)
{
	if (index1 == index2) return;

	arr[index1] = arr[index1] ^ arr[index2];
	arr[index2] = arr[index1] ^ arr[index2];
	arr[index1] = arr[index1] ^ arr[index2];
}

#define MAX(a,b) (a>b?a:b)

static void heapify(int* arr, const size_t arrSize, const int index)
{
	int left, right;
	int curIndex = index;
	while (curIndex < heapSize)
	{
		left = curIndex * 2 + 1;
		right = curIndex * 2 + 2;
		if ((left < heapSize) && (right < heapSize))
		{
			if (arr[curIndex] < MAX(arr[left], arr[right]))
			{
				if (arr[left] > arr[right])
				{
					swap(arr, left, curIndex);
					curIndex = left;
				}
				else
				{
					swap(arr, right, curIndex);
					curIndex = right;
				}
			}
			else
				break;
		}
		else if (left < heapSize)
		{
			if (arr[curIndex] < arr[left])
			{
				swap(arr, left, curIndex);
				curIndex = left;
			}
			else
				break;
		}
		else
			break;
	}
}

static void insert(int* arr, const size_t arrSize, const int index)
{
	++heapSize;
	if (heapSize == 1)
	{
		return;
	}

	int curIndex = index;
	int upIndex = (curIndex - 1) / 2;
	while ((upIndex < curIndex) && (arr[curIndex] > arr[upIndex]))
	{
		swap(arr, curIndex, upIndex);
		curIndex = upIndex;
		upIndex = (curIndex - 1) / 2;
	}
}

/**
 * 堆排序
 * @param fromSmallToLarge true: 从小到大排序; false: 从大到小排序
 */
static void heapSort(int* arr, const size_t arrSize, bool fromSmallToLarge)
{
	heapSize = 0;
	for (int i = 0; i < arrSize; i++)
	{
		insert(arr, arrSize, i);
	}

	for (int i = 0; i < arrSize; i++)
	{
		swap(arr, 0, --heapSize);
		heapify(arr, arrSize, 0);
	}

	if (!fromSmallToLarge)
	{
		int l = 0;
		int r = arrSize - 1;
		while (l < r)
		{
			swap(arr, l++, r--);
		}
	}
}

static void swapContinuousPart(int* arr, const int start1, const int end1, const int end2)
{
	if (start1 >= end2) return;

	int start2 = end1 + 1;
	int l = start1;
	int r = end1;
	while (l < r)
	{
		swap(arr, l++, r--);
	}

	l = start2;
	r = end2;
	while (l < r)
	{
		swap(arr, l++, r--);
	}

	l = start1;
	r = end2;
	while (l < r)
	{
		swap(arr, l++, r--);
	}
}

static void perfectShuffle(int* arr, const size_t arrSize)
{
	if (!arr || arrSize == 0) return;

	assert(arrSize % 2 == 0 && "arrSize is odd number.");
	if (arrSize == 2)
	{
		swap(arr, 0, 1);
		return;
	}

	int pw = log(arrSize) / log(3);
	int k = pow(3, pw) - 1;
	swapContinuousPart(arr, k / 2, arrSize / 2 - 1, arrSize / 2 + k / 2 - 1);

	int start, tmp, tmp2, cur, next;
	for (int n = 0; n < k; n++)
	{
		start = pow(3, n) - 1;
		if (start>=k) break;

		cur = start;
		tmp = arr[cur];
		do 
		{
			if (cur < k / 2)
			{
				next = cur * 2 + 1;
			}
			else
			{
				next = (cur - k / 2) * 2;
			}

			tmp2 = arr[next];
			arr[next] = tmp;
			tmp = tmp2;
			cur = next;
		} while (cur != start);
	}

	if (arrSize - k > 0)
	{
		perfectShuffle(arr + k, arrSize - k);
	}
}

static void specialSort(int* arr, const size_t arrSize)
{
	if (!arr || arrSize <= 1)return;

	if (arrSize == 2)
	{
		if (arr[0] > arr[1]) swap(arr, 0, 1);
		return;
	}

	heapSort(arr, arrSize, arrSize % 2);

	if (arrSize % 2)
	{
		perfectShuffle(arr + 1, arrSize - 1);
	}
	else
	{
		perfectShuffle(arr, arrSize);
	}
}

/**
 * 一个整数无序数组arr，请对它进行重新排列，使它形成： [a,b,c,d,e,f,g,h,...]
 * a≤b≥c≤d≥e≤f≥g≤h...，要求空间复杂度O(1)
 * 
 * 思路：
 * 1. 将arr按照堆排序的方式排序。因为只有堆排序满足空间复杂度O(1),而且最快
 * 2. 倘若arr.Length是偶数，则先对arr从大到小排序，再进行完美洗牌即可达成目的；但是arr.Length是奇数，则需要先把arr从小到大排序，然后从arr[1]开始(也就是排除第0个元素)，针对后面的元素，进行完美洗牌。
 * 
 * 完美洗牌请参考代码: PerfectShuffle.cpp
 */
int main_oneBigOneSmall()
{
	int arr[] = { 5,4,7,6,2,2,3,1,9,8,10,10 };
	auto arrSize = sizeof(arr) / sizeof(int);
	specialSort(arr, arrSize);

	for (int i = 0; i < arrSize; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n");

	return 0;
}